#ifndef GAMEENGINE_CORE_GRAPH_OCTREE_NODE_HPP
#define GAMEENGINE_CORE_GRAPH_OCTREE_NODE_HPP

#include <GameEngine/Core/Memory/memory_manager.h>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif


//=====================================================================


//! Default constructor
template <class E, class T>
OctreeNode<E,T>::OctreeNode() : children_(nil) {}

//! Constructor
/*!
 @param box The box associated to the octree node
 */
template <class E, class T>
OctreeNode<E,T>::OctreeNode(const Box3d<T>& box) : children_(nil), box_(box) {}

//! Copy constructor
/*!
 @param rhs The octree node to copy
 */
template <class E, class T>
OctreeNode<E,T>::OctreeNode(const OctreeNode& rhs) : children_(nil), box_(rhs.box_), elements_(rhs.elements_) {
	// Copy children if necessary
	if ( rhs.children_ != nil ) {
		subdivide();
		for ( int k = 0; k < 8; ++k ) children_[k] = rhs.children_[k];
	}
}

//! Destructor
template <class E, class T>
OctreeNode<E,T>::~OctreeNode() {
	MemoryManager::instance()->desallocate(children_,8);
}

//! Assignment operator
/*!
 @param rhs The octree node to copy
 */
template <class E, class T>
OctreeNode<E,T>& OctreeNode<E,T>::operator=(const OctreeNode& rhs) {
	if ( &rhs != this ) {
		box_ = rhs.box_;
		elements_ = rhs.elements_;
		if ( children_ != nil ) {
			MemoryManager::instance()->desallocate(children_,8);
			children_ = nil;
		}
		if ( rhs.children_ != nil ) {
			subdivide();
			for ( int k = 0; k < 8; ++k ) children_[k] = rhs.children_[k];
		}
	}
	return *this;
}

//! Accessor to the children of the octree node (read only)
/*!
 @return A pointer to the children of the octree node (may be nil if the node has no children)
 */
template <class E, class T>
OctreeNode<E,T>* OctreeNode<E,T>::children() const {
	return children_;
}

//! Accessor to the box of the octree node (read only)
/*!
 @return A constant reference to the box of the octree node
 */
template <class E, class T>
const Box3d<T>& OctreeNode<E,T>::box() const {
	return box_;
}

//! Accessor to the elements of the octree node (read only)
/*!
 @return A constant reference to the elements of the octree node
 @note This function solely returns the elements associated to THIS node. All the
       elements associated to the children of this node are ignored.
 */
template <class E, class T>
const std::vector<E>& OctreeNode<E,T>::elements() const {
	return elements_;
}

//! Accessor to the elements of the octree node (read-write)
/*!
 @return A reference to the elements of the octree node
 @note This function solely returns the elements associated to THIS node. All the
       elements associated to the children of this node are ignored.
 */
template <class E, class T>
std::vector<E>& OctreeNode<E,T>::elements() {
	return elements_;
}

//! Subdivide the octree node into eight subnodes
/*!
 @return True if octree node could be subdivided, false otherwise. An octree node may not
         be subdivided if it already has children.
 @note The elements of this node are NOT distributed to the children nodes because no information
       is available on which subnode they should belong to.
 */
template <class E, class T>
bool OctreeNode<E,T>::subdivide() {
	if ( children_ != nil ) return false;

	// Divide octree node
	children_ = MemoryManager::instance()->allocate< OctreeNode<E,T> >(8);

	// Update children boxes
	Vector3d<T> middle = Vector3d<T>( Point3d<T>(0,0,0), box_.bottom_left_down() ) + Vector3d<T>( box_.bottom_left_down(), box_.top_right_up() ) / (T)2;
	children_[0].box_ = Box3d<T>(box_.bottom_left_down().x(), middle.x(), middle.y(), box_.top_right_up().y(), box_.bottom_left_down().z(), middle.z());
	children_[1].box_ = Box3d<T>(middle.x(), box_.top_right_up().x(), middle.y(), box_.top_right_up().y(), box_.bottom_left_down().z(), middle.z());
	children_[2].box_ = Box3d<T>(box_.bottom_left_down().x(), middle.x(), box_.bottom_left_down().y(), middle.y(), box_.bottom_left_down().z(), middle.z());
	children_[3].box_ = Box3d<T>(middle.x(), box_.top_right_up().x(), box_.bottom_left_down().y(), middle.y(), box_.bottom_left_down().z(), middle.z());
	children_[4].box_ = Box3d<T>(box_.bottom_left_down().x(), middle.x(), middle.y(), box_.top_right_up().y(), middle.z(), box_.top_right_up().z());
	children_[5].box_ = Box3d<T>(middle.x(), box_.top_right_up().x(), middle.y(), box_.top_right_up().y(), middle.z(), box_.top_right_up().z());
	children_[6].box_ = Box3d<T>(box_.bottom_left_down().x(), middle.x(), box_.bottom_left_down().y(), middle.y(), middle.z(), box_.top_right_up().z());
	children_[7].box_ = Box3d<T>(middle.x(), box_.top_right_up().x(), box_.bottom_left_down().y(), middle.y(), middle.z(), box_.top_right_up().z());

	// Return success
	return true;
}

//! Merge the children of the octree node into this octree node
/*!
 @param unique If set to true, forbids the element to be added multiple times to the node
               while merging
 @return True if octree node could be merged, false otherwise. An octree node may not
         be merged if it has no children.
 @note The elements of the children node are distributed to this octree node.
 */
template <class E, class T>
bool OctreeNode<E,T>::merge(bool unique) {
	if ( children_ == nil ) return false;

	// Distribute children elements
	for ( int k = 0; k < 8; ++k ) {
		// Add the elements of this child (ensuring their uniqueness)
		for ( std::vector<E>::iterator it = children_[k].elements_.begin(); it != children_[k].elements_.end(); ++it ) {
			add_element(*it, unique, false);
		}
	}

	// Clear children
	MemoryManager::instance()->desallocate(children_,8);
	children_ = nil;

	// Return success
	return true;
}

//! Try to add the element to the lower-level octree node that can be reached
/*!
 @param element The element to add
 @param location The location associated to the element
 @param unique If set to true, forbids the element to be added multiple times to the node
 @return True if the element could be added to this octree node or one of its children,
         false otherwise. An element may not be added if its location does not fit with the
		 box of the octree node, or if it does not fit to the uniqueness criterion.
 @note The children node are recursively tested to add the element.
 */
template <class E, class T>
bool OctreeNode<E,T>::add_element(const E& element, const Point3d<T>& location, bool unique) {
	// Check the location
	if ( box_.inside(location) == false ) return false;

	// Check uniqueness
	if ( unique == true ) {
		if ( find_element(element, true) == true ) return false;
	}

	// If the node has children, add the element to one of them
	if ( children_ != nil ) {
		// Iterate over the children
		for ( int k = 0; k < 8; ++k ) {
			if ( children_[k].add_element(element, location, false) == true ) return true;
		}
		return false; // Unexpected error (no child accepted the element/location)
	}

	// Add the element
	elements_.push_back(element);
	return true;
}

//! Try to add the element to the lower-level octree node that can be reached
/*!
 @param element The element to add
 @param location The location associated to the element
 @return True if the element could be added to this octree node or one of its children,
         false otherwise. An element may not be added if its location does not fit with the
		 box of the octree node.
 @note The children node are recursively tested to add the element.
 */
template <class E, class T>
bool OctreeNode<E,T>::add_element(const E& element, const Box3d<T>& location) {
	// Check the location
	if ( box_.overlap(location) == false ) return false;

	// If the node has children, add the element to one of them
	if ( children_ != nil ) {
		// Iterate over the children
		bool res = false;
		for ( int k = 0; k < 8; ++k ) {
			if ( children_[k].add_element(element, location) == false ) continue;
			res = true;
		}
		return res;
	}

	// Add the element
	elements_.push_back(element);
	return true;
}

//! Try to add the element to this octree node
/*!
 @param element The element to add
 @param unique If set to true, forbids the element to be added multiple times to the node
 @param check_children If unique is true, children are also queried to check the uniqueness
                       of the element only if check_children is also true
 @return True if the element could be added to this octree node, false otherwise. An
         element may not be added if it does not fit to the uniqueness criterion.
 @note Even if the node has children, they are NOT considered to add this element.
 */
template <class E, class T>
bool OctreeNode<E,T>::add_element(const E& element, bool unique, bool check_children) {
	// Check uniqueness of the element
	if ( unique == true ) {
		if ( find_element(element, check_children) == true ) return false;
	}

	// Add the element
	elements_.push_back(element);
	return true;
}

//! Try to remove the element from this octree node and its children
/*!
 @param element The element to remove
 @param recursive If set to true, children of the octree node are also recursively
                  considered to remove the element
 @return The number of elements that were removed from the octree
 */
template <class E, class T>
typename OctreeNode<E,T>::ElementCount OctreeNode<E,T>::remove_element(const E& element, bool recursive) {
	ElementCount res = 0;

	// Look for the elements of this octree node
	int i = 0;
	for ( std::vector<E>::iterator it = elements_.begin(); it != elements_.end(); ++it ) {
		++i;
		if ( *it == element ) {
			elements_.erase(it);
			++res;
			if ( it == elements_.end() ) break;
		}
	}

	// Look for the children nodes
	if ( recursive == true ) {
		if ( children_ != nil ) {
			for ( int k = 0; k < 8; ++k ) {
				res += children_[k].remove_element(element, true);
			}
		}
	}

	// Return the result
	return res;
}

//! Try to find the element in this octree node and its children
/*!
 @param element The element to find
 @param recursive If set to true, children of the octree node are also recursively
                  considered to find the element
 @return True if element could be found, false otherwise
 */
template <class E, class T>
bool OctreeNode<E,T>::find_element(const E& element, bool recursive = true) const {
	// Look for the elements of this octree node
	for ( std::vector<E>::const_iterator it = elements_.begin(); it != elements_.end(); ++it ) {
		if ( *it != element ) continue;
		return true;
	}

	// Look for the children nodes
	if ( recursive == true ) {
		if ( children_ != nil ) {
			for ( int k = 0; k < 8; ++k ) {
				if ( children_[k].find_element(element, true) == true ) return true;
			}
		}
	}

	// Return the result
	return false;
}

//! Count the number of elements in this octree node
/*!
 @param recursive If set to true, children of the octree node are also recursively
                  considered to count the elements
 @return The number of elements in this octree node (and possibly, of its children)
 */
template <class E, class T>
typename OctreeNode<E,T>::ElementCount OctreeNode<E,T>::nb_elements(bool recursive) const {
	ElementCount res = (ElementCount)elements_.size();

	// Recursive counting
	if ( recursive == true ) {
		if ( children_ != nil ) {
			// Count the elements of the children
			for ( int k = 0; k < 8; ++k ) {
				res += children_[k].nb_elements(true);
			}
		}
	}

	// Return result
	return res;
}

//! Test if this octree node is non-empty
/*!
 @return True if this octree node is non-empty, false otherwise. Children nodes,
         if any, are ignored by this function.
 */
template <class E, class T>
bool OctreeNode<E,T>::is_non_empty() const {
	return ( elements_.empty() == false );
}

//! Test if this octree node is a low-level node
/*!
 @return True if this octree node is a low-level node, false otherwise. Children
         nodes, if any, are ignored by this function.
 */
template <class E, class T>
bool OctreeNode<E,T>::is_low_level() const {
	return ( children_ == nil );
}

//! Get the low-level octree node that covers the given location
/*!
 @param location The location that should be queried
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
const OctreeNode<E,T>* OctreeNode<E,T>::get_node(const Point3d<T>& location) const {
	// Test the box
	if ( box_.inside(location) == false ) return nil;

	// Test if node has children
	if ( children_ == nil ) return this;
	for ( int k = 0; k < 8; ++k ) {
		const OctreeNode<E,T>* node = children_[k].get_node(location);
		if ( node == nil ) continue;
		return node->get_node(location);
	}

	// Unexpected error (location did not belong to any children)
	return nil;
}

//! Get the low-level octree node that covers the given location
/*!
 @param location The location that should be queried
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
OctreeNode<E,T>* OctreeNode<E,T>::get_node(const Point3d<T>& location) {
	// Test the box
	if ( box_.inside(location) == false ) return nil;

	// Test if node has children
	if ( children_ == nil ) return this;
	for ( int k = 0; k < 8; ++k ) {
		OctreeNode<E,T>* node = children_[k].get_node(location);
		if ( node == nil ) continue;
		return node->get_node(location);
	}

	// Unexpected error (location did not belong to any children)
	return nil;
}

//! Get the octree nodes that cover the given location
/*!
 @param location The location that should be queried
 @param type The type of nodes to be considered
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
std::list<const OctreeNode<E,T>*> OctreeNode<E,T>::get_nodes(const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type) const {
	std::list<const OctreeNode<E,T>*> res;
	get_nodes_recursive(*this, res, location, type);
	return res;
}

//! Get the octree nodes that cover the given location
/*!
 @param location The location that should be queried
 @param type The type of nodes to be considered
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
std::list<OctreeNode<E,T>*> OctreeNode<E,T>::get_nodes(const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type) {
	std::list<OctreeNode<E,T>*> res;
	get_nodes_recursive(*this, res, location, type);
	return res;
}

//! Get the octree nodes that cover the location
/*!
 @param node The node to be considered (children are also recursively considered if
             the box of the node overlaps given location)
 @param list Receives the list of nodes that cover the location
 @param location The location to be queried
 @param type The type of nodes that should be considered
 */
template <class E, class T>
bool OctreeNode<E,T>::get_nodes_recursive(const OctreeNode<E,T>& node, std::list<SelfPtrConst>& list,
								  const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type)
{
	// Test location
	if ( node.box_.overlap(location) == false ) return false;

	// Add this node if it fits to the desired type of nodes
	bool low_level = node.is_low_level();
	if ( type == OctreeNodeItr::LowLevelNodes ) {
		if ( low_level ) list.push_back(&node);
	}
	else if ( type == OctreeNodeItr::NonEmptyNodes ) {
		if ( node.is_non_empty() ) list.push_back(&node);
	}
	else list.push_back(&node);

	// Consider children, if any
	if ( low_level == false ) {
		for ( int k = 0; k < 8; ++k ) {
			get_nodes_recursive(node.children_[k], list, location, type);
		}
	}

	// Return success
	return true;
}

//! Get the octree nodes that cover the location
/*!
 @param node The node to be considered (children are also recursively considered if
             the box of the node overlaps given location)
 @param list Receives the list of nodes that cover the location
 @param location The location to be queried
 @param type The type of nodes that should be considered
 */
template <class E, class T>
bool OctreeNode<E,T>::get_nodes_recursive(OctreeNode<E,T>& node, std::list<SelfPtr>& list,
								  const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type)
{
	// Test location
	if ( node.box_.overlap(location) == false ) return false;

	// Add this node if it fits to the desired type of nodes
	bool low_level = node.is_low_level();
	if ( type == OctreeNodeItr::LowLevelNodes ) {
		if ( low_level ) list.push_back(&node);
	}
	else if ( type == OctreeNodeItr::NonEmptyNodes ) {
		if ( node.is_non_empty() ) list.push_back(&node);
	}
	else list.push_back(&node);

	// Consider children, if any
	if ( low_level == false ) {
		for ( int k = 0; k < 8; ++k ) {
			get_nodes_recursive(node.children_[k], list, location, type);
		}
	}

	// Return success
	return true;
}


//=====================================================================


//! Constructor
/*!
 @param node The node to iterate
 @param type The type of the nodes on which to iterate (can be all nodes, low-level nodes or non-empty nodes)
 */
template <class O>
OctreeNodeIterator<O>::OctreeNodeIterator(O& node, OctreeNodeItr::OctreeNodeItrType type) :
	node_(nil), next_node_(nil)
{
	// Setup the correct functions
	if ( type == OctreeNodeItr::AllNodes ) {
		pop_func_ = &OctreeNodeIterator::pop_node_all;
	}
	else if ( type == OctreeNodeItr::NonEmptyNodes ) {
		pop_func_ = &OctreeNodeIterator::pop_node_non_empty;
	}
	else {
		pop_func_ = &OctreeNodeIterator::pop_node_low_level;
	}

	// Add the node and its first children, if any
	push_node(node);

	// Get the first node
	next_node_ = nodes_to_explore_.rbegin()->first;
	next();
}

//! Destructor
template <class O>
OctreeNodeIterator<O>::~OctreeNodeIterator() {}

//! Test if the iterator has more nodes to consider after the current one
/*!
 @return True if more nodes are available, false otherwise
 */
template <class O>
bool OctreeNodeIterator<O>::more() const {
	return ( node_ != nil );
}

//! Head to the next node of the iterator
template <class O>
void OctreeNodeIterator<O>::next() {
	// Transfer the next node
	node_ = next_node_;
	if ( next_node_ == nil ) return;

	// Update the next node
	pop_node();
	if ( nodes_to_explore_.empty() ) next_node_ = nil;
	else next_node_ = nodes_to_explore_.rbegin()->first;
}

//! Accessor to the current node of the iterator (read-write)
/*!
 @return A reference to the current node of the iterator
 */
template <class O>
O& OctreeNodeIterator<O>::cur() {
	return *node_;
}

//! Accessor to the current node of the iterator (read only)
/*!
 @return A constant reference to the current node of the iterator
 */
template <class O>
const O& OctreeNodeIterator<O>::cur() const {
	return *node_;
}

//! Add the node to the list of nodes to consider
/*!
 @param node The node to add
 */
template <class O>
void OctreeNodeIterator<O>::push_node(O& node) {
	// Build the iteration structure
	std::pair<O*,int> itr(&node,-1);

	// Test if the node has children
	O* children = node.children();
	if ( children != nil ) itr.second = 0;

	// Add the node to the list
	nodes_to_explore_.push_back(itr);

	// If the node has children, recursively add the first child
	if ( itr.second >= 0 ) {
		push_node(children[0]);
	}
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeIterator<O>::pop_node() {
	(this->*pop_func_)();
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeIterator<O>::pop_node_low_level() {
	// Remove the last node
	nodes_to_explore_.pop_back();

	// Test the list of nodes
	if ( nodes_to_explore_.empty() ) return;

	// Get the current last node
	std::pair<O*,int>& itr = *nodes_to_explore_.rbegin();
	++itr.second;
	if ( itr.second < 8 ) {
		push_node(*(itr.first->children()+itr.second));
	}
	else {
		pop_node_low_level();
	}
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeIterator<O>::pop_node_all() {
	// Remove the last node
	nodes_to_explore_.pop_back();

	// Test the list of nodes
	if ( nodes_to_explore_.empty() ) return;

	// Get the current last node
	std::pair<O*,int>& itr = *nodes_to_explore_.rbegin();
	++itr.second;
	if ( itr.second < 8 ) {
		push_node(*(itr.first->children()+itr.second));
	}
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeIterator<O>::pop_node_non_empty() {
	// Remove the last node
	nodes_to_explore_.pop_back();

	// Test the list of nodes
	if ( nodes_to_explore_.empty() ) {
		if ( node_ ) {
			if ( node_->elements().empty() ) {
				node_ = nil;
				next_node_ = nil;
			}
		}
		return;
	}

	// Get the current last node
	std::pair<O*,int>& itr = *nodes_to_explore_.rbegin();
	++itr.second;
	if ( itr.second < 8 ) {
		push_node(*(itr.first->children()+itr.second));
	}

	// Check if the node is non-empty
	if ( node_ == nil ) return;
	if ( node_->elements().empty() ) {
		// Head to the next node
		if ( nodes_to_explore_.empty() ) next_node_ = nil;
		else next_node_ = nodes_to_explore_.rbegin()->first;
		next();
	}
}

//=====================================================================


//! Constructor
/*!
 @param node The node to iterate
 @param type The type of the nodes on which to iterate (can be all nodes, low-level nodes or non-empty nodes)
 */
template <class O>
OctreeNodeConstIterator<O>::OctreeNodeConstIterator(const O& node, OctreeNodeItr::OctreeNodeItrType type) :
	node_(nil), next_node_(nil)
{
	// Setup the correct functions
	if ( type == OctreeNodeItr::AllNodes ) {
		pop_func_ = &OctreeNodeConstIterator::pop_node_all;
	}
	else if ( type == OctreeNodeItr::NonEmptyNodes ) {
		pop_func_ = &OctreeNodeConstIterator::pop_node_non_empty;
	}
	else {
		pop_func_ = &OctreeNodeConstIterator::pop_node_low_level;
	}

	// Add the node and its first children, if any
	push_node(node);

	// Get the first node
	next_node_ = nodes_to_explore_.rbegin()->first;
	next();
}

//! Destructor
template <class O>
OctreeNodeConstIterator<O>::~OctreeNodeConstIterator() {}

//! Test if the iterator has more nodes to consider after the current one
/*!
 @return True if more nodes are available, false otherwise
 */
template <class O>
bool OctreeNodeConstIterator<O>::more() const {
	return ( node_ != nil );
}

//! Head to the next node of the iterator
template <class O>
void OctreeNodeConstIterator<O>::next() {
	// Transfer the next node
	node_ = next_node_;
	if ( next_node_ == nil ) return;

	// Update the next node
	pop_node();
	if ( nodes_to_explore_.empty() ) next_node_ = nil;
	else next_node_ = nodes_to_explore_.rbegin()->first;
}

//! Accessor to the current node of the iterator
/*!
 @return A constant reference to the current node of the iterator
 */
template <class O>
const O& OctreeNodeConstIterator<O>::cur() {
	return *node_;
}

//! Add the node to the list of nodes to consider
/*!
 @param node The node to add
 */
template <class O>
void OctreeNodeConstIterator<O>::push_node(const O& node) {
	// Build the iteration structure
	std::pair<const O*,int> itr(&node,-1);

	// Test if the node has children
	O* children = node.children();
	if ( children != nil ) itr.second = 0;

	// Add the node to the list
	nodes_to_explore_.push_back(itr);

	// If the node has children, recursively add the first child
	if ( itr.second >= 0 ) {
		push_node(children[0]);
	}
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeConstIterator<O>::pop_node() {
	(this->*pop_func_)();
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeConstIterator<O>::pop_node_low_level() {
	// Remove the last node
	nodes_to_explore_.pop_back();

	// Test the list of nodes
	if ( nodes_to_explore_.empty() ) return;

	// Get the current last node
	std::pair<const O*,int>& itr = *nodes_to_explore_.rbegin();
	++itr.second;
	if ( itr.second < 8 ) {
		push_node(*(itr.first->children()+itr.second));
	}
	else {
		pop_node_low_level();
	}
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeConstIterator<O>::pop_node_all() {
	// Remove the last node
	nodes_to_explore_.pop_back();

	// Test the list of nodes
	if ( nodes_to_explore_.empty() ) return;

	// Get the current last node
	std::pair<const O*,int>& itr = *nodes_to_explore_.rbegin();
	++itr.second;
	if ( itr.second < 8 ) {
		push_node(*(itr.first->children()+itr.second));
	}
}

//! Remove the last node in the list of nodes to consider and try to expand the next node
template <class O>
void OctreeNodeConstIterator<O>::pop_node_non_empty() {
	// Remove the last node
	nodes_to_explore_.pop_back();

	// Test the list of nodes
	if ( nodes_to_explore_.empty() ) {
		if ( node_ ) {
			if ( node_->elements().empty() ) {
				node_ = nil;
				next_node_ = nil;
			}
		}
		return;
	}

	// Get the current last node
	std::pair<const O*,int>& itr = *nodes_to_explore_.rbegin();
	++itr.second;
	if ( itr.second < 8 ) {
		push_node(*(itr.first->children()+itr.second));
	}

	// Check if the node is non-empty
	if ( node_ == nil ) return;
	if ( node_->elements().empty() ) {
		// Head to the next node
		if ( nodes_to_explore_.empty() ) next_node_ = nil;
		else next_node_ = nodes_to_explore_.rbegin()->first;
		next();
	}
}

//=====================================================================


#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
